package 数据结构和算法.剑指offer.递归和循环.数值的整数次方;

import 工具.打印.PrintUtil;

/**
 * 实现函数double Power(double base, int exponent)，求base的exponent次方。
 * 不得使用库函数，同时不需要考虑大数问题。
 * <p>
 * 经典的二分快速幂
 */
public class Test {
    public static void main(String[] args) {
        PrintUtil.println(powOne(2, 2));
        PrintUtil.println(powTwo(2, 4));
    }

    // java库函数 Math.pow(x,n);
    public static double powOne(double x, int n) {
        return Math.pow(x, n);
    }

    // 使用二分快速幂
    public static double powTwo(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (n == -1) {
            return 1 / x;
        }
        if (n % 2 == 0) {
            double t = powTwo(x, n / 2);
            return t * t;
        } else {
            double t = powTwo(x, n / 2);
            if (n < 0) {
                x = (1 / x);
            }
            return t * t * x;
        }
    }

}
